Wagner and Fischer first defined the simple version of the edit distance problem. Given two sequences (strings) A = a1a2a3... am and B = b1b2b3... bm, the edit distance problem is to find a series of edit operations with the minimum cost to transform A into B. The allowed edit operations include character insertion, character deletion and character replacement. They proposed a dynamic programming (DP) approach to solve the problem. Their algorithm calculates each cell of DP lattice in O(1) time and the size of DP lattice is O(nm), so the time complexity is O(mn).
int WagnerFischer_Alg(char *stringA, char *stringB, int m, int n)
{
int i, j, **matrix;
int lcs = 0;
//memAllocMatrix
matrix = (int**) calloc(m + 2, sizeof(int*));
for (i = 0; i < m + 2; i++){
matrix[i] = (int*) calloc(n + 2, sizeof(int));
}
//initialize
for (i = 0; i <= m; i++){
matrix[0][i] = i;
}
for (i = 0; i <= n; i++){
matrix[i][0] = i;
}
// mainProcess
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
if (stringA[i] == stringB[j]){
matrix[i][j] = matrix[i - 1][j - 1];
}
else{
matrix[i][j] = min(min(matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + 2), matrix[i - 1][j] + 1);
}
}
}
lcs=(m + n - matrix[m][n]) / 2;
for (i = 0; i < m + 2; i++){
free(matrix[i]);
}
free(matrix);
return lcs;
}